#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
struct node{
    int x, y, d;
    bool operator < (const node &a) const{
        return d > a.d; // 小根堆：d小的优先
    }
};

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

void solve()
{
    int n,m;
    cin >> n >> m;
    vector<int> arr(n + 10);
    for(int i = 1; i <= n; i ++) cin >> arr[i];
    for(int i = 1; i <= n; i ++) arr[i] -= i;

    int left = 1;
    multiset <int> xgd;
    multiset <int,greater <int>> dgd;
    int s1 = 0,s2 = 0;
    for(int i = 1; i <= n; i ++)
    {
        if(dgd.empty())
        {
            xgd.insert(a[i]);
            s2 += a[i];
        }
        else
        {
            if (a[i] > *dgd.begin()) xgd.insert(a[i]),s2 += a[i];
            else dgd.insert(a[i]),s1 += a[i];
        }
        while (judge(dgd.size(),xgd.size()) > 1) {
            if (dgd.size() > xgd.size()) {
                ll x = *dgd.begin();
                s2 += x;s1 -= x;
                xgd.insert(x);dgd.erase(dgd.begin());
            } 
            else {
                ll x = *xgd.begin();
                s1 += x;s2 -= x;
                dgd.insert(x);xgd.erase(xgd.begin());
            }
        }
        ll val1 = 0;
        if (dgd.size() >= xgd.size()) {
            val1 = *dgd.begin();
        } else {
            val1 = *xgd.begin();
        }
    }


}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}